package net.tp.algo.heap;

import net.tp.util.StepLogger;
import net.tp.struct.tree.TreePrinter;
import net.tp.util.Wrappers;
import net.tp.struct.tree.BinNode;

import java.util.Comparator;
import java.util.Stack;
import java.util.logging.Level;
import java.util.logging.Logger;

/**
 *
 * Cartesian Tree.
 * <p>
 * Cartesian Tree has the following properties:
 * <ul>
 *  <li>Heap properties: parent of any non-root nodes have smaller value</li>
 *  <li>The symmetric in-order traversal of the tree results in the original sequence.</li>
 * </ul>
 *
 * <pre>
 * Elements: [9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5]
 *
 * Step 0: insert 9
 * 9
 * Stack: [9]
 *
 * Step 1: insert 3
 *  3
 * ┌┴┐
 * 9
 * Stack: [3]
 *
 * Step 2: insert 7
 *  3
 * ┌┴┐
 * 9 7
 * Stack: [3, 7]
 *
 * Step 3: insert 1
 *   1
 *  ┌┴─┐
 *  3
 * ┌┴┐
 * 9 7
 * Stack: [1]
 *
 * Step 4: insert 8
 *   1
 *  ┌┴─┐
 *  3  8
 * ┌┴┐
 * 9 7
 * Stack: [1, 8]
 *
 * Step 5: insert 12
 *    1
 *  ┌─┴─┐
 *  3   8
 * ┌┴┐ ┌┴┐
 * 9 7   12
 * Stack: [1, 8, 12]
 *
 * Step 6: insert 10
 *    1
 *  ┌─┴─┐
 *  3   8
 * ┌┴┐ ┌┴┐
 * 9 7   10
 *       ┌┴─┐
 *       12
 * Stack: [1, 8, 10]
 *
 * Step 7: insert 20
 *    1
 *  ┌─┴─┐
 *  3   8
 * ┌┴┐ ┌┴┐
 * 9 7   10
 *       ┌┴─┐
 *       12 20
 * Stack: [1, 8, 10, 20]
 *
 * Step 8: insert 15
 *    1
 *  ┌─┴─┐
 *  3   8
 * ┌┴┐ ┌┴┐
 * 9 7   10
 *       ┌┴─┐
 *       12 15
 *          ┌┴─┐
 *          20
 * Stack: [1, 8, 10, 15]
 *
 * Step 9: insert 18
 *    1
 *  ┌─┴─┐
 *  3   8
 * ┌┴┐ ┌┴┐
 * 9 7   10
 *       ┌┴─┐
 *       12 15
 *          ┌┴─┐
 *          20 18
 * Stack: [1, 8, 10, 15, 18]
 *
 * Step 10: insert 5
 *      1
 *  ┌───┴────┐
 *  3        5
 * ┌┴┐  ┌────┴────┐
 * 9 7  8
 *     ┌┴┐
 *       10
 *       ┌┴─┐
 *       12 15
 *          ┌┴─┐
 *          20 18
 * Stack: [1, 5]
 * </pre>
 *
 * @author Trung Phan
 *
 */
public class CartesianTree<E> {

    private static Logger logger = Logger.getLogger(CartesianTree.class.getName());

    private final Comparator<? super E> comparator;

    private BinNode<E> root;

    /**
     *
     * @param elements initial elements for the tree
     * @param comparator element comparator
     *
     * @time $O(n)$
     */
    public CartesianTree(Iterable<E> elements, Comparator<? super E> comparator) {

        StepLogger stepLogger = new StepLogger(logger.isLoggable(Level.FINE));
        stepLogger.log("Elements: %s\n\n", Wrappers.iterableToString(elements));

        this.comparator = comparator;

        Stack<BinNode<E>> stack = new Stack<>();

        for (E element : elements) {
            if (root == null) {
                root = new BinNode<>(element);
                stack.push(root);
            }
            else if (comparator.compare(root.element, element) >= 0) {
                BinNode<E> node = new BinNode<>(element);
                node.left = root;
                root = node;
                stack.clear();
                stack.add(node);
            }
            else {
                while (comparator.compare(stack.peek().element, element) >= 0) stack.pop();
                BinNode<E> node = new BinNode<>(element);
                node.left = stack.peek().right;
                stack.peek().right = node;
                stack.push(node);
            }

            stepLogger.log("Step %d: insert %s\n", stepLogger.getStep(), element.toString());
            stepLogger.log("%s\n", this);
            stepLogger.log("Stack: %s\n\n", stack);
            stepLogger.incrementStep();
        }

        if (logger.isLoggable(Level.FINE)) {
            logger.fine(stepLogger.toString());
        }
    }

    public BinNode<E> getRoot() {
        return this.root;
    }

    @Override
    public String toString() {
        return TreePrinter.toString(root);
    }


    public static void main(String ... args) {

        int[] a = {9, 3, 7, 1, 8, 12, 10, 20, 15, 18, 5};
        CartesianTree<Integer> cartesianTree = new CartesianTree<>(Wrappers.makeIterable(a), Comparator.naturalOrder());

        System.out.println(cartesianTree);
    }
}
